"""
1. 斐波那契数列
    fn = fn-1 + fn-2

    递归(慢)：子问题的重复计算, 相同的问题算了好多遍
    f(5) = f(4) + f(3)
    f(4) = f(3) + f(2)
    f(3) = f(2) + f(1)
    f(2) = 1


    非递归：
    1, 1, 2, 3, 5
    
    
    # 递归慢是不断的对子问题进行求解
    1. 求 f(5) 的 时候要求 f(4) f(3) f(2) f(1)
    2. 接下来求 f(4) 要求 f(3) f(2) f(1)
    3. f(3) 要求 f(2) f(1)
    也就是说子问题在递归例不断被计算
"""


# 递归
def getN(n: int):
    if n == 1 or n == 2:
        return 1
    
    return getN(n-1) + getN(n - 2)

data = getN(10)
print(data)

"""
    动态规划是一种思想，避免子问题重复计算
    我们将之前的结果进行一个存储避免重复计算
"""

def getN2(n: int):
    a = [1, 1]
    i = 2
    if n > 2:  
        while i < n:
            a.append(a[i-1] + a[i-2])
            i += 1
    return a[n - 1]

data = getN2(1)
print(data)


def getN3(n: int):
    a = 1
    b = 1
    if n > 2:
        i = 2
        while i < n:
            a,b = b, a+b
            i += 1
        return b
             
    return 1
data = getN3(3)
print(data)